package org.leetcode.middle.leetcode148;

import org.leetcode.middle.ListNode;

import java.util.Arrays;

public class Solution
{

    public ListNode sortList3(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }


    public ListNode sortList2(ListNode head){

        ListNode temp = head;

        int size =0;

        while (temp!=null){
            size++;
            temp= temp.next;
        }

        if (size==0 || size==1){
            return head;
        }

        temp=head;
        int [] arr = new int[size];

        for (int i = 0; i < size; i++) {
            arr[i]=temp.val;
            temp=temp.next;
        }

        sort(arr);

        ListNode res = new ListNode();

        ListNode res2=res;

        res.val=arr[0];

        for (int i = 1; i < size; i++) {
            res.next=new ListNode();
            res=res.next;
            res.val=arr[i];
        }

        return res2;
    }

    private void sort(int [] arr){

        int length = arr.length;

        int [] helper = new int[length];

        split(arr,0,length-1,helper);

    }

    private void split(int [] arr,int left, int right,int [] helper){
        if (left==right){
            return;
        }

        int mid =(left+right)>>>1;

        split(arr,left,mid,helper);
        split(arr,mid+1,right,helper);

        merge(arr,left,mid,mid+1,right,helper);

        System.arraycopy(helper,left,arr,left,right-left+1);

    }

    private void merge(int [] arr,int i,int iEnd,int j,int jEnd,int [] helper){
        int cur = i;

        while (i<=iEnd && j<=jEnd){
            if (arr[i]<arr[j]){
                helper[cur]=arr[i];
                i++;
            }else {
                helper[cur]=arr[j];
                j++;
            }
            cur++;
        }

        if (i>iEnd){
            System.arraycopy(arr,j,helper,cur,jEnd-j+1);
        }

        if (j>jEnd){
            System.arraycopy(arr,i,helper,cur,iEnd-i+1);
        }
    }
    //超时
    public ListNode sortList(ListNode head) {

        if (head==null || head.next ==null )
        {
            return head;
        }

        ListNode current = head;

        int size =0;

        while (current!=null) {
            size++;
            current=current.next;
        }

        current=head;

        ListNode next = current.next;


        for (int i = 0; i < size-1; i++) {

            for (int j = 0; j < size-1-i; j++) {
                if (current.val>next.val)
                {
                    int temp = current.val;
                    current.val=next.val;
                    next.val=temp;
                }

                current=current.next;
                next = current.next;
            }

            current=head;
            next=current.next;
        }


        return head;
    }

    public static void main(String[] args) {
        ListNode test = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));

        Solution solution = new Solution();

        ListNode listNode = solution.sortList2(test);
    }
}
